package 代码随想录_动态规划.背包_01;

/**
 * @author zx
 * @create 2022-05-24 10:36
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
 * 2.确定递推公式
 *  dp[j]有两个选择，一个是取自己dp[j]，一个是取dp[j - weight[i]] + value[i]，指定是取最大的，毕竟是求最大价值
 *  dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 * 3.dp数组如何初始化
 *  dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了
 * 4.确定遍历顺序
 *  一维dp遍历的时候，背包是从大到小。倒叙遍历是为了保证物品i只被放入一次！
 * 5.举例推导dp数组
 *
 *
 * 如果一旦正序遍历了，那么物品0就会被重复加入多次
 * 一定要倒叙遍历，保证物品0只被放入一次！这一点对01背包很重要
 * 二维的思路参考九章算法,但是滚动数组的优化思路参考代码回想录
 */

/**
 * 01背包:
 * 有N件物品和一个最多能背重量为W 的背包.第i件物品的重量是weight[i],
 * 得到的价值是value[i].每件物品只能用一次,求将哪些物品装入背包里物品价值总和最大
 *
 * 01背包问题,它的特点是：[每个数只能用一次];解决的基本思路是：物品一个一个选,容量也一点一点增加去考虑
 * 背包问题一般都可以进行一维(滚动数组)优化,主要关注一维
 * 一维dp数组的写法，比较直观简洁，而且空间复杂度还降了一个数量级！
 */
public class lintcode125_背包问题二 {
    /**
     * @param m 大小为 m 的背包
     * @param a 数组 a 表示每个物品的大小
     * @param v 数组 v 表示每个物品的价值
     *
     * @return (题型一)：求将哪些物品装入背包里物品价值总和最大
     *
     * 滚动数组优化(代码随想录)
     */
    public int backPackII3(int m, int[] a, int[] v) {
        int[] dp = new int[m + 1];//容量为w的背包,所背的物品价值可以最大为dp[w]。
        //初始化
        for(int i = 0;i <= m;i++){
            dp[i] = 0;
        }
        for(int i = 0;i < a.length;i++){//遍历物品
            for(int j = m;j >= a[i];j--){//遍历背包容量
                dp[j] = Math.max(dp[j],dp[j - a[i]] + v[i]);
            }
        }
        return dp[m];
    }





    /**
     * @param m 大小为 m 的背包
     * @param a 数组 a 表示每个物品的重量大小
     * @param v 数组 v 表示每个物品的价值
     * @return
     */
    //背包容量w为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0
    public int backPackII(int m, int[] a, int[] v) {
        int[][] dp = new int[a.length + 1][m + 1];
        //f[i][w] = 用前i个物品拼出重量w时最大总价值(-1表示不能拼出w)
        //初始化
        dp[0][0] = 0;
        for (int w = 1; w <= m; w++) {
            dp[0][w] = -1;//0个物品不能拼出任何重量
        }
        //计算
        for (int i = 1; i <= a.length; i++) {
            for (int w = 0; w <= m; w++) {
                if(w < a[i - 1]){
                    dp[i][w] = dp[i - 1][w]; // case 1
                }
                if (w >= a[i - 1] && dp[i - 1][w - a[i - 1]] != -1) { // case 2
                    //选择一：如果前n-1个物品能拼出w,最大总价值是v,前n个物品也能拼出w并且总价值是v
                    //选择二：如果前n-1个物品能拼出w-A_n-1,最大总价值是v,则再加上最后一个物品(重量A_n-1,价值V_n-1)
                    //       能拼出w,总价值是 V + V_n - 1
                    dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - a[i - 1]] + v[i - 1]);
                }
            }
        }
        //求结果
        int res = 0;
        for (int w = 0; w <= m; w++) {
            if (dp[a.length][w] != -1) {
                res = Math.max(res, dp[a.length][w]);
            }
        }
        return res;
    }
}
